from collections import defaultdict


class TreeNode:

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        h = defaultdict(int)
        h[0] = 1

        def f(root, tot):
            if root is None:
                return 0
            tot += root.val
            ans = h[tot - targetSum]
            h[tot] += 1
            ans += f(root.left, tot)
            ans += f(root.right, tot)
            h[tot] -= 1
            return ans

        return f(root, 0)
